﻿\newpage
\section{Введение}
\label{section:intro}

Данная работа представляет собой теоретическое и экспериментальное
исследование свойств важного класса формальных языков. Необходимые
определения приведены в разделе~\ref{section:theory}.
В работе рассматривается метод вычисления верхних оценок индексов
роста языков, избегающих экспоненты. Изучение таких языков является одной
из центральных тем в комбинаторике слов: ещё в 1906 году Туэ показал
(\cite{Thue}), что квадраты избегаемы над тернарным алфавитом, а кубы~--- над бинарным.
В 1972 Дежан сформулировала (\cite{Dejean}) гипотезу, по которой для каждого размера
алфавита определено значение {\it границы повторяемости}~--- максимальной экспоненты, неизбежной
над данным алфавитом. В 2010 году эта гипотеза была доказана
(\cite{Carpi-Dejean,CR-Dejean,Rao-Dejean}). В работе \cite{Shur-Algo} предложен
алгоритм, позволяющий вычислять верхние оценки индексов роста языков, избегающих
экспоненты. Мы рассматриваем модификацию этого алгоритма для случая больших
алфавитов и маленьких экспонент. Эта модификация позволяет сократить
время работы и объём используемой памяти и, следовательно, получить более точные
оценки индексов роста, используя те же вычислительные ресурсы.

Также в работе приведено исследование языков, избегающих абелевы экспоненты.
Избегаемость целых абелевых степеней хорошо изучена (\cite{Keranen, Carpi-1, Dekking, ACR, Currie}),
однако до сих пор не существует общепризнанного определения дробных абелевых степеней.
Мы приводим три различных определения дробных абелевых степеней, рассматриваем
для каждого определения метод вычисления верхних оценок индексов роста языков,
избегающих абелевы экспоненты, и исследуем значения абелевой границы повторяемости.

Практической целью этой работы было создание эффективной программы, позволяющей
вычислять верхние оценки индексов роста языков, избегающих обычные и абелевы
экспоненты, а также получение оценок значений абелевой границы повторяемости
для различных определений дробной абелевой степени.

В разделе \ref{section:theory} изложены основные понятия, определения и факты,
используемые в данной работе.

В разделе \ref{section:bigexp} описан метод, позволяющий получать оценки индексов
роста языков, избегающих малые экспоненты (при размере алфавита $k \ge 4$ и экспоненте
$\beta \le \frac{k-1}{k-2}$), и численные результаты, полученные с его помощью.

В разделе \ref{section:abelian} приведены различные определения дробных абелевых
степеней, нетривиальные нижние оценки абелевой границы повторяемости, алгоритм
вычисления индексов роста языков, избегающих абелевы экспоненты, численные
результаты и основанные на них гипотезы.

%введение\\ ok
%Актуальность\\ ok
%Новизна и обзор\\ ok
%Цели и задачи\\ ok
%Объёкт и предмет исследования\\ ok
%Методы\\ ???
%Структура работы\\ ok
